package com.rran.study.algorithm.easy.day07;

import com.rran.study.algorithm.medium.day06.ListNode;

import java.util.Stack;

/**
 * @author yy
 * @Type Solution.java
 * @Desc 反转一个单链表。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * <p>
 * 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 * @date 2020/9/9
 */
public class Solution01 {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(4);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(9);
        ListNode l5 = new ListNode(9);
        l1.setNext(l2);
        l2.setNext(l3);
        l3.setNext(l4);
        l4.setNext(l5);
        Solution01 solution = new Solution01();
        ListNode result = solution.reverseList(l1);
        result.printListNode(result);
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null; //前指针节点
        ListNode curr = head; //当前指针节点
        //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
        while (curr != null) {
            ListNode nextTemp = curr.getNext(); //临时节点，暂存当前节点的下一节点，用于后移
            curr.setNext(prev); //将当前节点指向它前面的节点
            prev = curr; //前指针后移
            curr = nextTemp; //当前指针后移
        }
        return prev;
    }
}
